﻿/************************************************************************
 * AIDE - Automata Identification Engine
 * Copyright (C) 2012-2013 Ali Khalili (khalili_DOT_ir_@SIGN_gmail_DOT_com)
 * **********************************************************************
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License (LGPL) published 
 * by the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version. This program is distributed without any
 * warranty. See the GNU Lesser General Public License for more details. 
 * ***********************************************************************
 * File         :     AIDE\Utils\Tree.cs
 * Description  :     Structure of tree
 * Change log   :     -Dec 2012: initil version
 * To Do        :
 ************************************************************************/

using System;
using System.Collections.Generic;
using System.Text;

namespace AIDE.Utils
{
    /// <summary>
    /// A general tree structure where you can define data type of nodes and edges and number of childs varies in different nodes
    /// [suggestion: keep data of node and edge together!]
    /// </summary>
    /// <typeparam name="NodeData">Type of nodes, use class nothing if you don'anotherRow have any special data to be stored in nodes</typeparam>
    /// <typeparam name="EdgeData">Type of edges, use class nothing if you don'anotherRow have any special data to be stored in edges</typeparam>
    public class Tree<NodeData, EdgeData>
    {
        #region Internal Class

        /// <summary>
        /// Tree Node
        /// </summary>
        public class TreeNode
        {
            List<TreeNode> childs;
            List<EdgeData> edges;
            NodeData data;

            /// <summary>
            /// Constructor
            /// </summary>
            /// <param name="data"></param>
            public TreeNode(NodeData data)
            {
                childs = new List<TreeNode>();
                this.data = data;
                edges = new List<EdgeData>();
            }


            /// <summary>
            /// List of edges
            /// </summary>
            public List<EdgeData> Edges
            {
                get
                {
                    return edges;
                }
            }

            public NodeData NodeObject
            {
                get
                {
                    return data;
                }
				set
				{
					data=value;
				}
            }

            /// <summary>
            /// List of childs
            /// </summary>
            public List<TreeNode> Childs
            {
                get
                {
                    return childs;
                }
            }

            /// <summary>
            /// number of childs in the node
            /// </summary>
            public int NumberOfChilds
            {
                get { return childs.Count; }
            }


            /// <summary>
            /// Add a child to this node
            /// </summary>
            /// <param name="data">label of edge</param>
            /// <param name="edge">label of the node corresponding to the child</param>
            public TreeNode AddChild(NodeData data, EdgeData edge)
            {
                TreeNode ch = new TreeNode(data);
                edges.Add(edge);
                childs.Add(ch);
                return ch;
            }

            /// <summary>
            /// Add a child when the node (child) is already constructed
            /// </summary>
            /// <param name="next">the child</param>
            /// <param name="edge">transition to child</param>
            /// <returns>the child</returns>
            public TreeNode AddChild(TreeNode next, EdgeData edge)
            {
                edges.Add(edge);
                childs.Add(next);
                return next;
            }

            /// <summary>
            /// Find child by index
            /// </summary>
            /// <param name="indx"></param>
            /// <returns></returns>
            public TreeNode ChildByIndex(int indx)
            {
                if (indx >= 0 && indx < NumberOfChilds)
                    return childs[indx];
                else
                    return null;
            }

            /// <summary>
            /// Find child by edge
            /// </summary>
            /// <param name="edge"></param>
            /// <returns></returns>
            public TreeNode ChildByEdge(EdgeData edge)
            {
                for (int i = 0; i < edges.Count; i++)
                    if (edges[i].Equals(edge))
                        return childs[i];
                return null;

            }

            /// <summary>
            /// Change (set) the node data
            /// </summary>
            /// <param name="d">the data to be replaced for this node's value</param>
            public void SetNodeObject(NodeData d)
            {
                this.data = d;
            }

            /// <summary>
            /// Consider a node as a tree. Check that it is equal to another node (as a tree) OR NEG
            /// </summary>
            /// <param name="node2">the other node</param>
            /// <returns></returns>
            public bool EqualsAsTree(Tree<NodeData, EdgeData>.TreeNode node2)
            {
                if (NumberOfChilds != node2.NumberOfChilds)
                    return false;

                for (int i = 0; i < NumberOfChilds; i++)
                {
                    EdgeData ed = edges[i];
                    TreeNode myNode = node2.ChildByEdge(ed);
                    if (myNode == null) return false;
                    if (!(myNode.EqualsAsTree(childs[i])))
                        return false;
                }
                return true;
            }

			public override string ToString ()
			{
				string str = (data == null ? "" : data.ToString());
				foreach (EdgeData e in edges)
					str += e.ToString ();
				return str;
			}
        }

        #endregion

        TreeNode root;

        public Tree(NodeData root_data = default(NodeData))
        {
            root = new TreeNode(root_data);
        }

        public Tree(TreeNode node)
        {
            root = node;
        }

        public TreeNode Root
        {
            get { return root; }
        }


        /// <summary>
        /// Check the equality of two trees
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public override bool Equals(object obj)
        {
            if (!(obj is Tree<NodeData, EdgeData>))
                return false;
            Tree<NodeData, EdgeData> tr = (Tree<NodeData, EdgeData>)obj;
            return Root.EqualsAsTree(tr.Root);
        }

        /// <summary>
        /// Get hash code of a tree.
        /// Neg implemented. Just to avoid warning!
        /// </summary>
        /// <returns></returns>
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }

        //public static explicit operator Tree<NodeData, EdgeData>(TreeNode node)
        //{
        //    new Exception("Neg implemented");
        //    return null;
        //}


        public List<TreeNode> Leaves()
        {
            new Exception("Not implemented");
            return null;
        }

		/// <summary>
		/// Export the tree as dot format
		/// </summary>
		/// <returns>dot format</returns>
		public string ExportAsDot ()
		{
			StringBuilder dot = new StringBuilder ();
			dot.AppendLine ("Digraph myTree{");
			List<Tree<NodeData, EdgeData>.TreeNode> nodes = new List<Tree<NodeData, EdgeData>.TreeNode> ();
			nodes.Add (this.root);
			//* explore the tree (bfs)
			while (nodes.Count!=0) {
				Tree<NodeData, EdgeData>.TreeNode curr = nodes [0];
				nodes.RemoveAt(0);
				for (int i=0; i<curr.NumberOfChilds; i++) {
					dot.AppendLine ("\""+curr.NodeObject.ToString () + "\" -> \"" + curr.Childs [i].NodeObject.ToString() +
					                "\" [ label=\"" + curr.Edges [i].ToString() + "\"]");
					nodes.Add (curr.Childs [i]);
				}
			}
			dot.AppendLine ("}");
			return dot.ToString ();			         
		}
    }

    /// <summary>
    /// A general tree structure where you can define data type of nodes and edges and number of childs varies in different nodes
    /// [suggestion: keep data of node and edge together!]
    /// </summary>
    /// <typeparam name="NodeData">Type of nodes, use class nothing if you don'anotherRow have any special data to be stored in nodes</typeparam>
    /// <typeparam name="EdgeData">Type of edges, use class nothing if you don'anotherRow have any special data to be stored in edges</typeparam>
    public class Tree<EdgeData>
    {
        #region Internal Class

        /// <summary>
        /// Tree Node
        /// </summary>
        public class TreeNode
        {
            List<TreeNode> childs;
            List<EdgeData> edges;
            //NodeData data;

            /// <summary>
            /// Constructor
            /// </summary>
            /// <param name="data"></param>
            public TreeNode(/*NodeData data*/)
            {
                childs = new List<TreeNode>();
                //this.data = data;
                edges = new List<EdgeData>();
            }


            /// <summary>
            /// List of edges
            /// </summary>
            public List<EdgeData> Edges
            {
                get
                {
                    return edges;
                }
            }

            /// <summary>
            /// List of childs
            /// </summary>
            public List<TreeNode> Childs
            {
                get
                {
                    return childs;
                }
            }

            /// <summary>
            /// number of childs in the node
            /// </summary>
            public int NumberOfChilds
            {
                get { return childs.Count; }
            }


            /// <summary>
            /// Add a child to this node
            /// </summary>
            /// <param name="edge">label of the node corresponding to the child</param>
            /// <returns>the generated child</returns>
            public TreeNode AddChild(/*NodeData data, */EdgeData edge)
            {
                TreeNode ch = new TreeNode(/*data*/);
                edges.Add(edge);
                childs.Add(ch);
                return ch;
            }

            /// <summary>
            /// Find child by index
            /// </summary>
            /// <param name="indx"></param>
            /// <returns></returns>
            public TreeNode ChildByIndex(int indx)
            {
                if (indx >= 0 && indx < NumberOfChilds)
                    return childs[indx];
                else
                    return null;
            }

            /// <summary>
            /// Find child by edge
            /// </summary>
            /// <param name="edge"></param>
            /// <returns></returns>
            public TreeNode ChildByEdge(EdgeData edge)
            {
                for (int i = 0; i < edges.Count; i++)
                    if (edges[i].Equals(edge))
                        return childs[i];
                return null;
            }

            /// <summary>
            /// Consider a node as a tree. Check that it is equal to another node (as a tree) OR NEG
            /// </summary>
            /// <param name="node2">the other node</param>
            /// <returns></returns>
            public bool EqualsAsTree(Tree</*NodeData, */EdgeData>.TreeNode node2)
            {
                if (NumberOfChilds != node2.NumberOfChilds)
                    return false;

                for (int i = 0; i < NumberOfChilds; i++)
                {
                    EdgeData ed = edges[i];
                    TreeNode myNode = node2.ChildByEdge(ed);
                    if (myNode == null) return false;
                    if (!(myNode.EqualsAsTree(childs[i])))
                        return false;
                }
                return true;
            }

            //public override string ToString()
            //{
            //    return this.
            //}
        }

        #endregion

        TreeNode root;

        public Tree(/*NodeData root_data = default(NodeData)*/)
        {
            root = new TreeNode(/*root_data*/);
        }

        public Tree(TreeNode node)
        {
            new Exception("Not implemented");
        }

        public TreeNode Root
        {
            get { return root; }
        }


        public override string ToString()
        {
            if (root == null)
                return "NULL";

            string[] tillHere = new string[20];
            int[] tmp = new int[20];
            Tree<EdgeData>.TreeNode[] tillHereNodes = new Tree<EdgeData>.TreeNode[20];

            string str = "";
            for (int i = 0; i < 20; i++)
            {
                tillHere[i] = "";
                tmp[i] = 0;
            }
            Tree<EdgeData>.TreeNode currentNode = root;
            int currentDepth = 0;

            //* find the first leaf
            while (currentNode.Edges.Count > 0)
            {
                tillHereNodes[currentDepth] = currentNode;
                tillHere[currentDepth] = currentNode.Edges[0].ToString();
                currentNode = currentNode.Childs[0];
                currentDepth++;
                if (currentDepth > 19)
                    return "Error: Max depth is 20!";
            }


            while (true)
            {
                //* reach a leaf
                if (currentNode.Edges.Count == 0)
                {
                    //* add it to the output set
                    string tmpStr = "";
                    for (int u = 0; u < currentDepth; u++)
                        tmpStr += tillHere[u] + (u == currentDepth - 1 ? "" : ",");
                    str += tmpStr;

                    //* return up to the root
                    for (int i = currentDepth; i > 0; i--)
                    {
                        tmp[i] = 0;
                        currentDepth--;
                        currentNode = tillHereNodes[currentDepth];
                        tmp[currentDepth]++;
                        if (tmp[currentDepth] < currentNode.Edges.Count)
                        {
                            //tmp[currentDepth]++;
                            break;
                        }
                    }
                    if (currentDepth == 0 && tmp[currentDepth] >= currentNode.Edges.Count)
                        break;
                    else
                        str += " + ";
                }
                //* go down in the tree
                else
                {

                    tillHereNodes[currentDepth] = currentNode;
                    tillHere[currentDepth] = currentNode.Edges[tmp[currentDepth]].ToString();

                    currentNode = currentNode.Childs[tmp[currentDepth]];
                    currentDepth++;
                    if (currentDepth > 19)
                        return "Error: Max depth is 20!";
                }
            }
            return str;
        }

        /// <summary>
        /// Check the equality of two trees
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public override bool Equals(object obj)
        {
            if (!(obj is Tree</*NodeData,*/ EdgeData>))
                return false;
            Tree</*NodeData,*/ EdgeData> tr = (Tree</*NodeData, */EdgeData>)obj;
            return Root.EqualsAsTree(tr.Root);
        }

        /// <summary>
        /// Get hash code of a tree.
        /// Neg implemented. Just to avoid warning!
        /// </summary>
        /// <returns></returns>
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }

        //public static explicit operator Tree<NodeData, EdgeData>(TreeNode node)
        //{
        //    new Exception("Neg implemented");
        //    return null;
        //}


        public List<TreeNode> Leaves()
        {
            new Exception("Not implemented");
            return null;
        }


    }
}
